package com.hyper_yang.algorithmRecord;

// 爬楼梯
public class LeetCode_70 {
//    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    public static void main(String[] args) {
        System.out.println(climbStairs(4));
    }
    // 动态规划 (同 fibonacci):
    public static int climbStairs1(int n) { // 状态转移方程: f(n) = f(n-1) + f(n-2)
        int pre2 = 1, pre1 = 1;
        int countN = 1;
        for (int i = 1; i < n; i++) {
            countN = pre2 + pre1;
            pre2 = pre1;
            pre1 = countN;
        }
        return countN;
    }
    // 数学公式法:
    public static int climbStairs(int n) {
        double sqrt_5 = Math.sqrt(5);
        double fib = (Math.pow((1+sqrt_5)/2,n+1)-Math.pow((1-sqrt_5)/2,n+1)) / sqrt_5;
        return (int)fib;
    }
}
